Podczas studiów odbywał częste podróże po kraju i malował pejzaże oraz sceny rodzajowe z udziałem ludności miast, miasteczek oraz wsi, utrwalając obrazy z życia codziennego tamtych czasów. Kostrzewski wraz z kolegami ze studiów, między innymi Wojciechem Gersonem, Juliuszem Kossakiem i Henrykiem Pillatim, stworzyli grupę artystyczną zwaną „cyganerią” malarską, skupioną wokół postaci Marcina Olszyńskiego, ich mecenata i serdecznego przyjaciela. Owocem ich wspólnej pracy były tzw. „Albumy”, zawierające szkice z wędrówek i życia codziennego grupy przyjaciół.

W 1856 roku odbył kilkumiesięczną podróż artystyczną przez Niemcy do Paryża. Po powrocie do Polski w 1856 roku rozpoczął działalność ilustratorską, w 1870 roku całkowicie już niemal porzuciwszy malarstwo. Jego ilustracje ukazywały się w czasopismach warszawskich – „Tygodniku Ilustrowanym”, „Kłosach”, „Musze”, „Wędrowcu” i innych. Ilustrował także książki, m.in. Bolesława Prusa i Józefa Ignacego Kraszewskiego. Pochowany na cmentarzu Powązkowskim (kwatera 181-4-20/21).