•A novel Feature Engineering solution for theft detection in Smart Grids is introduced.•Demand data from more than 4000 households are used to benchmark the solution.•Six different attack scenarios and five machine learning algorithms are examined.•Gradient Boosting is deployed and shown to outperform previous fraud detection models.•Effects of unforeseen, zero-day, and irregular attacks are examined. Despite many potential advantages, Advanced Metering Infrastructures have introduced new ways to falsify meter readings and commit electricity theft. This study contributes a new model-agnostic, feature-engineering framework for theft detection in smart grids. The framework introduces a combination of Finite Mixture Model clustering for customer segmentation and a Genetic Programming algorithm for identifying new features suitable for prediction. Utilizing demand data from more than 4000 households, a Gradient Boosting Machine algorithm is applied within the framework, significantly outperforming the results of prior machine-learning, theft-detection methods. This study further examines some important practical aspects of deploying theft detection including: the detection delay; the required size of historical demand data; the accuracy in detecting thefts of various types and intensity; detecting irregular and unseen attacks; and the computational complexity of the detection algorithm.