У 1995–1998 рр. — заступник Міністра закордонних справ України. Відповідав за питання контролю над озброєнням, європейської безпеки, співпраці в рамках СНД, відносини з Росією, країнами Близького і Середнього Сходу, Азії, Африки та Тихоокеанського регіону. Очолював делегації України на переговорах з ряду принципово важливих для держави питань. Був заступником Голови Урядової комісії з політики експортного контролю. У цей період ініціював направлення новопризначених співробітників МЗС на навчання до США та Європи, що дозволило підготувати якісні кадри для міністерства.
З 1998 по 2000 рр. — Глава Місії України при НАТО, Посол України в Бельгії, Нідерландах та Люксембурзі<ref>[http://zakon2.rada.gov.ua/laws/show/869/98 Указ Президента України «Про призначення К.Грищенка Надзвичайним і Повноважним Послом України в Королівстві Бельгія та Главою Місії України при НАТО за сумісництвом» від 10 серпня 1998 року №869/98“]</ref>. В якості Глави місії при НАТО підтримував зміцнення взаємодії України з Альянсом та активне використання його можливостей для реформування оборонного сектору України. Водночас, під час операції НАТО в Югославії 1999 р. послідовно виступав проти застосування збройної сили та визнання незалежності Косово.
. В якості Глави місії при НАТО підтримував зміцнення взаємодії України з Альянсом та активне використання його можливостей для реформування оборонного сектору України. Водночас, під час операції НАТО в Югославії 1999 р. послідовно виступав проти застосування збройної сили та визнання незалежності Косово.
У січні 2000 р. Костянтин Грищенко був призначений Послом України у [[США|Сполучених Штатах]]<ref>[http://zakon0.rada.gov.ua/laws/show/107/2000 Указ Президента України «Про призначення К. Грищенка Надзвичайним і Повноважним Послом України в Сполучених Штатах Америки» від 28 січня 2000 року N 107/2000“]</ref> і у 2001 р. Послом у [[Антигуа]] та [[Барбуда]] за сумісництвом]]<ref>[http://zakon1.rada.gov.ua/laws/show/888/2001 Указ Президента України «Про призначення К. Грищенка Надзвичайним і Повноважним Послом України в Антигуа і Барбуда за сумісництвом» від 24 вересня 2001 року N 888/2001 “]</ref>.
У особистій якості брав участь у роботі низки авторитетних міжнародних структур: у 1991 р. — заступник Головного інспектора першої інспекції ООН з питань біологічної зброї в [[Ірак]]у; в 1995–1998 рр. — член Ради засновників Женевського центру політики у галузі безпеки; у 1999–2003 рр. — член Дорадчої ради з питань роззброєння при Генеральному секретареві ООН (у 2003 р. — Голова Ради) ; в 2000–2003 рр. — член Колегії уповноважених при Комісії за спостереженням, контролем та інспекціями в Іраку (ЮНМОВІК).