Александр Кулешов родился 2 мая 1946 года в городе Москва. В 1970 году окончил механико-математический факультет МГУ имени М.В.Ломоносова по специальности «Математика». С 1970 года по 1989 год Александр Петрович работал в Московском НПО «Кибернетика» на должностях инженера, старшего инженера, начальника отдела. В 1977 году защитил диссертацию кандидата технических наук.
С 1983 года занимал должность главного инженера на том же предприятии, а с 1984 года занимал должность первого заместителя директора Научно-тематического центра.
В 1987 году защитил диссертацию доктора технических наук. В 1989 году ему было присвоено звание профессора.
С 1989 года по 1992 год работал в Международном центре по информатике и электронике в должности первого заместителя генерального директора. С 1992 года по 2001 год являлся членом Совета директоров Московской компаний «Бизнес-связь» и Киевской компании «Укрсат».
С 2001 года по 2006 год Кулешов был директором Центра программных технологий РАН. C 2003 года - генеральным директором, позднее стал советником в Международном научно-исследовательском институте проблем управления. C 2006 года занял кресло директора Института проблем передачи информации имени А.А.Харкевича РАН, стал заведующим базовыми кафедрами в МФТИ. Также преподает в Высшей школе экономики.
В 2008 году, 29 мая, Александр Петрович был избран членом-корреспондентом РАН. Академиком РАН был избран 22 декабря 2011 года. С 15 февраля 2016 года Кулешов Александр Петрович приступил к исполнению обязанностей ректора Сколковского института науки и технологий.