1909년 경상북도 대구군[현 대구광역시]에서 태어났다.
교남학교 재학 중에 미술 교사의 추천으로 1925~1926년경 일본으로 미술 유학을 떠났다. 그러나 일본에서 사진으로 방향을 전환하였고, 교토[京都]의 영납사진기점에서 일하며 사진술을 배웠다. 이후 1933년 귀국하여 대구 종로1가에 최계복사진기점을 열고 본격적인 사진 활동을 시작하였다. 일본인 중심의 사진 단체가 세력을 확장하고 있던 시절, 서명직, 정운상, 조상규, 장병진 등과 함께 1934년에 한국인만으로 결성된 대구아마추어사우회를 조직하였다. 이 단체는 사진술 습득, 친목 도모, 정보 공유를 통해 아마추어 사진가들의 예술 사진 활동에 필요한 기반을 구축해 나갔으며, 같은 해 창립된 일본 사진가 모임인 대구사우회와 경쟁 구도를 형성하였다.
최계복은 「령선못의 봄」[1933]을 시작으로 본격적인 작품 활동을 시작한 이후, 수십 회에 이르는 공모전 당선으로 전국적 명성을 얻었다. 1936년에는 4월 대구부윤컵 대구사진공모전에서 「춘풍」이 입선한 것을 시작으로 같은 해에만 약 10회에 걸쳐 수상하였다. 한국인 입상이 쉽지 않았던 전조선사진공모전에서도 수상하였으며, 조선일보사 주최 납량사진현상모집에서도 1938년과 1939년에 연이어 1등으로 당선되었다. 1942년에는 조선산악회의 백두산 등정에 참가하여 수십 여장의 기록 사진을 찍기도 하였다.
해방 이후, 조선예술사진공모전 및 예술사진동인전에 참가하였다. 또한 경북사진문화연맹 결성과 한국사진작가협회 출범 등에 중추적인 역할을 하였다. 1947년에는 울릉도 · 독도 조사단에 참여하여 기록 사진을 남겼다. 한국전쟁 때는 촉탁 형식의 사진 대원으로 전쟁 현장을 기록하기도 하였다. 이후 1960년대에 미국으로 건너갔다.
일제강점기 예술 사진 개념은 제국주의적 시각이나 식민지 지배를 위한 담론과의 연관성 속에 확대되는 한편, 한국인의 민족문화적 정체성 재현이라는 당위성 속에서 공모전이나 전시회 등을 통해서도 확대되어 갔다. 1930년대의 최계복은 이러한 역사적 상황과 사회 문화 담론을 바탕으로 사진 작업을 진행하였다. 실제로 1930년대 최계복의 사진에 드러난 ‘향토색’은 당시 한국 미술인들에게 유일한 발표의 장이었던 조선미술전람회에 출품된 여타 예술 작품의 흐름과 맥을 함께한다. 그의 작품은 주로 한국인의 일상생활과 자연적 요소를 주제로, 서정성과 민족문화적 특성을 드러내는 것들이었다.
「령선못의 봄」, 「대합실, 경주역」[1939] 등의 작품에서 드러나듯이 그의 초기 작품에는 주1 형식과 고무 인화 방식 등 회화적인 인화 기법이 주로 사용되었다. 이러한 기법은 일제강점기 당시 공모전이나 사진 전람회 등의 제도에서 선호되었던 예술 사진 작업 방식으로, 한국 사진가들뿐만 아니라 일본 사진가들에 의해서도 빈번히 채택되던 방식이다. 스트레이트한 촬영과 인화 방식을 채택한 이후에도 그의 작품은 회화적 구도와 미학적 기준을 충족시키려는 방향을 견지하였다.