Predictable internal climate variability on decadal timescales (2-10 years) is associated with large-scale oceanic processes, however these predictable signals may be masked by the noisy climate system. One approach to overcoming this problem is investigating state-dependent predictability - how differences in prediction skill depend on the initial state of the system. We present a machine learning approach to identify state-dependent predictability on decadal timescales in the Community Earth System Model version 2 by incorporating uncertainty estimates into a regression neural network. We leverage the network’s prediction of uncertainty to examine state dependent predictability in sea surface temperatures by focusing on predictions with the lowest uncertainty outputs. In particular, we study two regions of the global ocean - the North Atlantic and North Pacific - and find that skillful initial states identified by the neural network correspond to particular phases of Atlantic multi-decadal variability and the interdecadal Pacific oscillation.