Родился в станице Должанской Ейского района Краснодарского края. Там же в 1935 г. окончил неполную среднюю школу-семилетку.
В 1939 г. Константин Максимович был призван в армию и направлен в Военно-Морской флот. На «Щ-408» служил командиром отделения СКС.
В качестве ближайших родственников он указал в анкете жену Галину Михайловну Горохову, проживавшую в Ленинграде, и мать Ефросинью Андреевну Самойленко, которая в тот момент жила в станице Должанской.