Evidence-based approaches to international policy-making may improve the quality of policy decisions compared to traditional decision making principles. For example, decision makers traditionally rely on existing administrative boundaries when establishing new international borders following the dissolution of a state or the secession of part of that state. An evidence-based alternative could involve consideration of numerous other factors and goals in establishing a border. Policy informatics, encompassing new knowledge, tools, and approaches should become increasingly useful for informing policy decisions, especially where decision makers are faced with a constant influx of information, conflicting values and political pressures. Specifically, a complexity approach has shown utility in effectively extracting useful patterns from complex landscapes in various science areas. However, its applications to public policy problems have been limited due to some unique obstacles and barriers inherent to these problems. Through the example of border resolutions, we examine the evolution of using scientific reasoning to make policy choices and how we might be able to include a complexity approach more regularly in evidence-based policy debates.