This paper describes the procedure and results of the building envelope optimization of a public building in Hrvatska Kostajnica. The building is very energy inefficient in its current condition. In order to make it energy efficient and closer to the concept of the nearly-zero energy building (nZEB), an energy model of the building has been created using the computer program TRNSYS®. The energy model was used to calculate hourly and annual heating and cooling energy needs. The existing condition of the envelope and current energy needs were a baseline for the optimization. An air-to-water heat pump was assumed to be the production system for heating and cooling energy. Heat pump coefficients of performance and the price/tariff of electricity were used to calculate annual operating expenses of the building. The first step in the optimization of the building envelope was to replace old, inefficient windows with new, double-paned or triple-paned insulated windows. This proved to be very energy efficient, resulting in substantial energy savings and savings in operating costs. The next step was to add thermal insulation on external walls in addition to the new windows. The combination of thermal insulation and new windows have resulted in even greater energy savings and the reduction in operating costs. Compared to the baseline, the annual heating need was reduced by 78,3%. However, the annual cooling need increased by 42,1% because the thermal insulation effects prevented the heat from escaping the building. As the last step, a shading system has been implemented, which also affected the energy needs. Specifically, it has significantly reduced the annual cooling needs. In conclusion, the total energy need for the building was reduced by 63% and the delivered (electrical) energy was reduced by 65,8%. Furthermore, the annual operating expenses were reduced by 60,6% and the return of investment equals to 139 years.