Родился 3 августа 1890 г. в Москве. Отец, Степан Илларионович, работал на строительстве дорог.
Уже в детстве у Константина Мельникова проявился талант к рисованию. В 1903 г. окончил четыре класса церковно-приходской школы. В том же году его родители познакомились с известным российским инженером и педагогом Владимиром Чаплиным, который взял 13-летнего Константина на воспитание в свою семью.
В 1905 г. Константин Мельников поступил в Московское училище живописи, ваяния и зодчества (МУЖВЗ, ныне Московский архитектурный институт и Московский государственный академический художественный институт имени В. И. Сурикова). В 1910 г. окончил сначала общеобразовательное отделение, а в 1914 г. - отделение живописи. После этого по настоянию Владимира Чаплина поступил на отделение архитектуры, где учился, в частности, у известного зодчего Ивана Жолтовского. Окончил МУЖВЗ в 1917 г. После этого стал архитектором-мастером Строительного отдела Моссовета.
Первые самостоятельные работы выполнил в духе неоклассицизма (нереализованные проекты застройки поселка Ходынского поля и Бутырского района).
В начале 1920-х гг. Константин Мельников стал одним из наиболее видных представителей архитектуры советского авангарда. С 1921 г. преподавал в Высших художественно-технических мастерских (ВХУТЕМАС). Затем, в 1927-1929 гг., - в Ленинградском высшем художественно-техническом институте (ВХУТЕИН).
Известность Константину Мельникову принес проект авангардистского деревянного павильона Всероссийского махорочного синдиката на Всероссийской сельскохозяйственной и кустарно-промышленной выставке 1923 г. (Москва; не сохранился). Похожий авангардный стиль в 1925 г. Мельников применил при проектировании павильона СССР на Международной выставке современных декоративных и промышленных искусств (Париж; не сохранился) и для ряда последующих выставочных павильонов СССР за рубежом.
В 1924 г. был автором саркофага для временного мавзолея Владимира Ленина.
Самая ранняя из сохранившихся архитектурных работ - здание конторы Ново-Сухаревского рынка в Москве (1924).
Расцвет творчества Мельникова пришелся на вторую половину 1920-х гг. В частности, в 1926 г. было завершено строительство Бахметьевского гаража (ныне часть его площадей занимает Еврейский музей и центр толерантности). В 1929 г. в Кривоарбатском переулке Константин Мельников построил свой дом-мастерскую. Он получил всемирную известность и является одним из наиболее ярких памятников советского авангарда. Постройка представляет собой два врезанных друг в друга вертикальных цилиндра разной высоты с оригинальными шестиугольными окнами и остекленным фасадом. В настоящее время здание передано в ведение Государственного музея архитектуры им. А. В. Щусева. В 1929 г. было завершено строительство еще одного ставшего впоследствии всемирно известным памятника - Клуба Русакова Союза коммунальников (ныне ДК им. И. В. Русакова, в нем работает Театр Романа Виктюка) в районе Сокольники. В 1930 г. по проекту Мельникова была выполнена планировка Центрального парка культуры и отдыха им. Горького в Москве и построен Дворец культуры Дулёвской фарфоровой фабрики (Ликино-Дулево, Московская обл.).
В 1930-х гг. на смену авангарду пришла эклектика ("сталинский ампир"). Константин Мельников участвовал в ряде архитектурных конкурсов. В частности, в 1934 г. он предложил авангардный проект для Наркомтяжпрома на Красной площади, а в 1952 г. - проект Пантеона на Ленинских горах. Почти все его проекты в этом периоде, за исключением зданий для нескольких ведомственных гаражей в Москве, не были реализованы, при этом их критиковали как "фантастические". Несмотря на это, в 1938 г. Константин Мельников получил пожизненную пенсию.
С конца 1940-х гг. Константин Мельников занимался, преимущественно, преподаванием. Сначала в Саратовском автодорожном институте (ныне Саратовский государственный технический университет имени Ю. А. Гагарина), затем в Московском инженерно-строительном институте (ныне Московский государственный строительный университет, МГСУ). С 1958 г. до конца жизни преподавал архитектурное проектирование, начертательную геометрию и графику во Всесоюзном заочном инженерно-строительном институте (ныне подразделение МГСУ).
В 1965 г., когда произошла переоценка тенденций развития архитектуры последних 20 лет, - как "сталинской" архитектуры, так и минимализма в строительстве во времена "хрущевской оттепели", - Мельников вновь получил признание. В 1965 г. ему была присвоена ученая степень доктора архитектуры без защиты диссертации, в 1972 г. - звание заслуженного архитектора РСФСР.
Скончался в Москве 28 ноября 1973 г. Похоронен на Введенском кладбище.
В 1967 г. написал автобиографическую монографию "Архитектура моей жизни" (опубликована в 1985 г.).
Был женат, супруга - Анна Яблокова; в семье было двое детей - дочь Людмила и сын Виктор.