Job is Storing History But 'Include Step Output in History' is not Checked
That check box does not prevent job step history from being recorded/stored. SQL Server is going to do all this by default and that I know of you cannot turn it off.

The check box referenced is for telling SQL Agent to store additional or more detailed job step output. It would store this information to msdb.dbo.sysjobstepslogs. Which from my testing just checking that box alone does not do anything. You would still find the table empty if you queried it. Once I also checked Log to table, ran the job again, and then it showed a record for the job step.

This would enabled on a job that runs DBCC CHECKFILEGROUP command for a database: