The effort estimation techniques used in the software industry often tend to ignore the impact of Non-functional Requirements (NFR) on effort and reuse standard effort estimation models without local calibration. Moreover, the effort estimation models are calibrated using data of previous projects that may belong to problem domains different from the project which is being estimated. The approach described in this thesis suggests a novel effort estimation methodology that can be used in the early stages of software development projects. The proposed methodology initially clusters the historical data from the previous projects into different problem domains and generates domain specific effort estimation models, each incorporating the impact of NFRs on effort by sets of objectively measured nominal features. The complexity of these models is reduced using a feature subset selection algorithm. In this thesis, our approach is discussed in detail, and the results of our experiments using different supervised machine learning algorithms are presented. The results show that our approach performs well by increasing the correlation coefficient and decreasing the error rate of the generated effort estimation models and achieving more accurate effort estimates for the new projects.