As software becomes more and more complex due to increased number of module size, procedure size, and branching complexity, software maintenance costs are often on the increase. Consider a software such as Windows 2000 operating systems with over 29 million lines of code (LOC), 480,000 pages if printed, a stack of paper 161 feet high, estimate of 63,000 bugs in the software when it was first released [1] and with over 1000 developers, there is no doubt that such a large and complex software will require large amount of money (in US Dollars), social and environmental factors to maintain it. It has been estimated that over 70% of the total costs of software development process is expended on maintenance after the software has been delivered. This paper studies the relationship between software complexity and maintenance cost, the factors responsible for software complexity and why maintenance costs increase with software complexity. Some data collected on Windows, Debian Linux, and Linux Kernel operating systems were used. The results of our findings show that there is a strong correlation between software complexity and maintenance costs. That is, as lines of code increase, the software becomes more complex and more bugs may be introduced, and hence the cost of maintaining software increases.