Воспитывался в петербургском доме графа А. С. Строганова как незаконнорождённый сын его сестры. В 1783 году выпущен из Пажеского корпуса в капитаны лейб-гренадерского полка. В 1785 году перешёл секунд-майором в Волынский регулярный казачий полк. В 1786 причислен к коллегии иностранных дел. Принимал участие в войне со Швецией 1788—1790 годов, был прикомандирован к главнокомандующему гребным флотом. За отличие в сражении при острове Мусала 13 августа 1789 года был произведён в полковники. Участвовал в подавлении восстания 1794 под руководством Костюшко в Польше и Литве. Выйдя в 1796 году в отставку, жил в Лондоне. Слушал лекции по физике, математике и медицине.
Один из ближайших сподвижников Александра I в первые годы его правления, член т. н. «Негласного комитета». В 1803—1810 годах — президент Академии наук, попечитель Петербургского учебного округа. На годы президентства Новосильцева пришлось первое русское кругосветное плавание. С 1806 года член Российской академии. С 21 октября 1804 года товарищ министра юстиции с оставлением в прежних должностях. Член комиссии законов. Сопровождал Александра I в заграничных поездках. В начале 1805 с успехом выполнил возложенную на него миссию о заключении союза с Великобританией, избран почётным членом Вольного общества любителей словесности, наук и художеств. Также состоял в столичной масонской ложе Соединённых друзей (Amis reunis).
После разочарования императора в Негласном комитете и его фактического роспуска Новосильцев в 1806 году был направлен послом к Наполеону, но не успел доехать до Парижа, как была объявлена последним война. Участвовал в событиях 1806—1809, состоя при императоре. В 1809—1812 годах жил в Вене, выполнял различные дипломатические поручения в Западной Европе. Новосильцев тяжело переживал удаление от двора, стал предаваться крепким напиткам.
В 1813—1815 годах вице-президент временного совета, управляющего Варшавским герцогством (впоследствии Царство Польское), позднее представитель императора Александра I при совете, управляющим Царством Польским, составил для него ряд проектов и учреждений, заведовал комитетом по учебной части. С 1821 года советник наместника Царства Польского и доверенное лицо великого князя Константина Павловича. Стал преемником Адама Чарторыйского на посту попечителя Виленского университета (1824—1831) и Виленского учебного округа. Возглавлял комиссию, расследовавшую тайные организации студентов Виленского университета (филоматы, филареты). Деятельность Новосильцева в Польше продолжалась до 1831. Обнаруженная им здесь строгость и даже жестокость, особенно по отношению к молодежи, вызвали ожесточение поляков и, по мнению некоторых, способствовали ускорению восстания 1830 года.
К 1820 году разработал проект «Уставной грамоты Российской империи» — первой конституции за всю историю России. Конституционный проект предусматривал создание двухпалатного парламента (Государственного сейма и Государственной думы), без которого монарх не мог издать ни одного закона, неприкосновенность собственности, независимость суда, равенство всех граждан перед законом, гражданские свободы, федеративное устройство России. Вопрос о крепостном праве в этом тайном проекте конституции не рассматривался. Этому были посвящены специальные, также сугубо секретные проекты, предлагавшиеся А. А. Аракчеевым и министром финансов Д. А. Гурьевым.
В 1821 году вместе с М. С. Воронцовым и А. С. Меншиковым разработал и представил Александру I проект отмены крепостного права (последствий не имел).
После Ноябрьского восстания (1830) Новосильцев вернулся из Польши в Петербург, где был назначен членом Государственног совета. Председатель Государственного совета (1834), кабинета министров (1832). В 1833 Новосильцеву пожалован титул графа.
Умер в 1838 году. Похоронен в Духовской церкви Александро-Невской лавры в Санкт-Петербурге. Обширное собрание бумаг Новосильцева сгорело большей частью во время польского восстания (1831), и только часть перешла к его племяннику...
Новосильцев прожил всю жизнь холостяком, но до старости слыл ловеласом («смесь Бахуса с сатиром»). П. В. Долгоруков характеризует его как «человека ума необыкновенного, обладавшего обширными сведениями и замечательным даром слова, но властолюбивого, коварного, бездушного и жестокого», прибавляя: «охотник до всех чувственных наслаждений». «Новосильцева я уже видел усталым человеком, пресыщенным волокитою, — вспоминает сенатор К. И. Фишер, — ничем не занимавшимся более, как обедами и волокитством: красное лицо, стеклянные глаза, вообще наружность, не обличающая государственного мужа…». Н. И. Греч вспоминал, что Новосильцев «в Вене упал и опошлился до невозможности и, странное дело в его положении и звании, — начал пить. Занимая уже первую ступень в государстве, он на годовом празднике Английского клуба плясал пьяный трепака пред многочисленным собранием. Зрелище грустное и оскорбительное для друга чести и добродетели!..»