ksh93 supports both completion and history. I lost interest in looking before uncovering information about versions of ksh more than thirty years old, but neither feature is mentioned in descriptions of differences between ksh93 and predecessors, so I suspect the feature has been there for longer. Posix compliance is neither necessary nor sufficient for a reasonable colloquial definition of "shell."
I believe it does log a short set of command history to a file, but it'd not available with, say, the up arrow.
In general, though, I don't think any form of history is required by the POSIX shell standard, and tab-completion definitely isn't.