The subject matter herein provides an automated system and method for software patch management that ranks patches at least in part according to a score indicative of a complexity (e.g., cost) of remediating a vulnerability. This score is sometimes referred to herein as a vulnerability remediation complexity (VRC) score. A VRC score provides an objective measure by which an organization can determine which patches are most likely to be successfully applied, thus enabling implementation of a patching strategy that preferentially applies most critical, but less impact (in terms of remediation cost) patches first to remediate as must risk as possible as quickly as possible. Thus, for example, the approach herein enables the patching to focus on vulnerabilities of highest severity and small remediation cost over those, for example, representing lower severity and higher remediation cost.