Capital structure of firms is an important aspect in finance which seeks to determine the optimal capital structure that a firm should maintain. Various theories have been put across to address this issue. This paper examines the relationship between capital structure and profitability of firms listed at the Nairobi Securities Exchange (NSE). The study employed a descriptive research design. A census study of 49 firms listed at the NSE that were operational from 2009 and 2013 was undertaken. These companies comprised of all the segments at NSE. Secondary data was collected for a period of five years from financial statements of the firms and the NSE handbook. The findings of the study indicated that capital structure had a significant negative influence on the profitability of firms listed at the NSE.