Non-binary Turbo codes have been shown to out-perform their binary counterparts in terms of error correcting performance yet the decoding complexity of the commonly used Min-Log-MAP algorithm prohibits efficient hardware implementations. In this work, we apply for the first time the recently proposed Local SOVA algorithm for decoding non-binary Turbo codes. Moreover, we propose a low complexity variant dedicated to the direct association with high order constellations denoted by the nearest neighbor Local SOVA. It considers only a limited amount of nearest competing constellation symbols for the soft output computation. Simulation results show that this approach allows a complexity reduction of up to 52% in terms of add-compare-select operations while maintaining the same error correcting performance compared to the Min-Log-MAP algorithm. It can even reach up to 80% if high code rates or frame error rates higher than 10−4 are targeted. The achieved complexity reduction represents a significant step forward towards hardware implementation.