Dengue is the commonest arboviral disease of humans. An early and accurate diagnosis of dengue can support clinical management, surveillance and disease control and is central to achieving the World Health Organisation target of a 50% reduction in dengue case mortality by 2020. 5729 children with fever of <72hrs duration were enrolled into this multicenter prospective study in southern Vietnam between 2010-2012. A composite of gold standard diagnostic tests identified 1692 dengue cases. Using statistical methods, a novel Early Dengue Classifier (EDC) was developed that used patient age, white blood cell count and platelet count to discriminate dengue cases from non-dengue cases. The EDC had a sensitivity of 74.8% (95%CI: 73.0-76.8%) and specificity of 76.3% (95%CI: 75.2-77.6%) for the diagnosis of dengue. As an adjunctive test alongside NS1 rapid testing, sensitivity of the composite test was 91.6% (95%CI: 90.4-92.9%). We demonstrate that the early diagnosis of dengue can be enhanced beyond the current standard of care using a simple evidence-based algorithm. The results should support patient management and clinical trials of specific therapies.