We present a frequency-domain method for computing the sensitivities of time-averaged quantities of chaotic systems with respect to input parameters. Such sensitivities cannot be computed by conventional adjoint analysis tools, because the presence of positive Lyapunov exponents leads to exponential growth of the adjoint variables. The proposed method is based on the well established least-square shadowing (LSS) approach [1], that formulates the evaluation of sensitivities as an optimisation problem, thereby avoiding the exponential growth of the solution. All existing formulations of LSS (and its variants) are in the time domain. In the present paper, we reformulate the LSS method in the frequency (Fourier) space using harmonic balancing. The resulting system is closed using periodicity. The new method is tested on the Kuramoto-Sivashinsky system and the results match with those obtained using the standard time-domain formulation. The storage and computing requirements of the direct solution grow rapidly with the size of the system. To mitigate these requirements, we propose a resolvent-based iterative approach that needs much less storage. Application to the Kuramoto-Sivashinsky system gave accurate results with low computational cost. Truncating the large frequencies with small energy content from the harmonic balancing operator did not affect the accuracy of the computed sensitivities. Further work is needed to assess the performance and scalability of the proposed method.