Родился в семье учителей начальной школы Алексея Фёдоровича и Веры Константиновны Рыбниковых (в будущем - Заслуженных учителей РСФСР). По отцовской линии предки были казаками, по материнской - священнослужителями. Имел старшего брата (сводного - от первого брака отца) и младших братьев Фёдора, Святослава и сестру Ольгу.
В 1929 году, после окончания средней школы-девятилетки (тогда учились 9 лет), хотел поступить в Ростовский университет, но получил отказ в приёме документов, поскольку места для будущих первокурсников распределялись по классовому принципу - среди детей рабочих и крестьян. Был зачислен в Краснодарское кавалерийское училище, однако из-за предполагаемого перевода во Владикавказское пехотное училище (где в то время был недобор курсантов) покинул училище. Вернулся в Миллерово и недолго работал на кирпичном заводе. По комсомольской путёвке получил направление на работу учителем начальной школы в село Позднеевка Криворожского района Ростовской области, в 40 км от Миллерово. Вёл уроки одновременно в нескольких классах. Затем преподавал (в том числе - и математику в классах всех уровней) в школах Миллерово.
В связи с начавшимся процессом создания украинских национальных кадров, получил направление для поступления в Киевский государственный университет и подал заявление на факультет социального воспитания, выпускники которого направлялись в общеобразовательные школы. Однако низкий уровень преподавания (велось на «ломаном» украинском языке, причем обучение математике было ниже всякой критики) побудил его вернуться в Миллерово.
Написал обстоятельное письмо ректору МГУ, в котором сообщал о себе и просил предоставить возможность учиться в университете заочно. В быстро полученном ответе сообщалось о его зачислении на первый курс заочного отделения механико-математического факультета (К. А. Рыбников подчеркивал, что его зачисление на факультет произошло ранее 1 мая 1933 года - ранее официальной даты создания механико-математического факультета) с приложением программы курса, контрольных заданий и учебной литературы.
В 1933 году, прибыв в Москву, успешно сдал экзамены за первый курс, а затем добился перевода на очное отделение, которое досрочно окончил в 1936 году. Ещё будучи студентом, познакомился со своей будущей женой Демидовой Антониной Андреевной, которая окончила химический факультет МГУ (впоследствии она заведовала кафедрой химии и биологии подготовительного отделения). Сам вольнослушателем окончил 4 курса химического факультета.
Был принят на работу в МГУ, два года заведовал учебной частью заочного отделения, а затем работал в должности заместителя ректора этого отделения. В 1938 году поступил в аспирантуру механико-математического факультета МГУ. Научным руководителем его стала С. А. Яновская. 25 июня 1941 года защитил кандидатскую диссертацию «К истории вариационного исчисления».
С началом Великой Отечественной войны участвовал в сооружении оборонительных сооружений по укреплению восточного берега Днепра. Затем был отправлен в Ленинградское высшее военно-инженерное училище им. А. А. Жданова (находившееся в эвакуации в Костроме), где комиссия отобрала его для учебы на Центральных курсах минных заграждений и особой техники. Получив там воинское звание старшины, был назначен старшиной роты особой техники. В мае 1942 года было присвоено звание лейтенанта, прошел стажировку в сапёрных частях на Калининском фронте. С 1943 года проходил службу в осаждённом Ленинграде, преподавал в военно-инженерном училище. С мая по октябрь 1944 года находился в действующих частях на фронте, командовал взводом сапёров (минёров). Участник операции «Багратион» при наступлении I Белорусского фронта, форсировал реку Березину, освобождал Бобруйск.
С 1945 года - доцент кафедры математики физического факультета МГУ. Получил направление на работу в специальную криптографическую службу, где проработал несколько лет. Майор ГБ.
С мая 1953 года - доцент механико-математического факультета. Читал курсы лекций по математическому анализу, высшей математике, истории математики, методологическим проблемам математики и комбинаторному анализу.
Доктор физико-математических наук, тема диссертации - «О работах К. Маркса по математике» (1954). Профессор (1956).
В 1959 году основал на мехмате МГУ кабинет истории и методологии математики и механики и был заведующим этим кабинетом вплоть до своей кончины. Главным направлением исследований сотрудников кабинета стала история отечественной математики и механики; исследовались также методологические проблемы развития науки, историографическая проблематика.
С августа 1959 по август 1960 года был начальником Главного управления университетов, экономических и юридических вузов Министерства высших учебных заведений РСФСР.
Учебник «История математики», написанный К. А. Рыбниковым, выдержал несколько изданий и был переведён на ряд языков. Этот учебник до сих пор остаётся на мехмате основным учебником по курсу истории математики.
Длительное время К. А. Рыбников был одним из руководителей Научно-исследовательского семинара по истории математики и механики, на базе которого сформировался ежегодник «Историко-математические исследования» - первое в мире периодическое издание по истории математики.
Под руководством К. А. Рыбникова защищено 32 кандидатских и 7 докторских диссертаций по пяти специальностям ВАК. Среди его учеников - С. С. Демидов, О. В. Иванов, Н. Н. Яковлев.