Brain Strokes are a leading cause of physical disabilities, damage of the brain and mortality affecting across the globe. Brain Stroke raises a serious health concern owing to interruption in the blood flow to the brain and it needs immediate treatment. This condition leads to the damage of brain cells of a person. Early identification of this condition is exigent for preventing disease progression and implementing successful treatment strategies. With the evolution of computer vision (CV), Computer-Aided Detection (CAD) technologies have demonstrated a new pathway towards the success in brain stroke diagnosis. This work investigates the potential of Local Directional Octa Pattern (LDOP), a simple and powerful local descriptor to identify brain stroke promptly and accurately at its early stage. The LDOP is very efficient in extraction of fine details of local features from Computed Tomography (CT) scan images, such as bleeding or blocked blood vessels in the brain, to successfully discriminate between normal and stroke affected brain. The proposed LDOP based brain stroke detection model attained the best accuracy of 99.31% by using top most similar images using Sum of Absolute Differences (SAD) classifier. Empirical outcomes of this study demonstrated the potential of LDOP in stroke detection at its early stage. Therefore, LDOP based models can be embedded in clinical decision support systems to provide timely, reliable and accurate early Brain Stroke diagnosis.