In Malaysia, there is a profusion of evidence of high graduate unemployment since many graduates are found lacking of what are needed to acquire and to maintain their jobs. In this paper, graduate employability skills were analyzed based on four major criteria: Qualification, academic score, experience and specific soft skills. The data and information used were extracted from 300 online job advertisements accessed via electronic databases at http://www.JobStreet.com.my from January to March 2011. A simple checklist form was developed to quantify the information from ads into quantitative data that was later keyed in the Statistical Package for Social Science for descriptive analyses. Based on the data, it was concluded that graduates with bachelor degrees were more likely to be employable due to high demand. It was also found that academic excellence based on CGPA was not the utmost factor for graduate employability. However, since less than one-third ads were free from work experiences requirement, fresh graduates only secured a little chance to be recruited. Another factor that limited graduates employability was high demand of specific soft skills requested by employers, among which were graduates with high quality of communication/interpersonal skills, foreign language proficiency, ICT/technical skills, high spirit of teamwork and specific personal attributes. Results concluded that graduate unemployment rate will continue to increase unless the Higher Education Institution (HEI) and the graduates are prepared to sharpen their soft skills according to market niche. It is suggested that the HEI work more closely with industries, professional bodies and society through the establishment of university-industry link cooperation that will become a catalyst for soft skills enhancement.