We have a SharePoint online tenant with Office E3 license, but when i access the Office 365 i can not find the Office 365 Videos app? so is this a license issue? or i need to create/configure the Office 365 portal first so users can start using it?
Stream replaces Office 365 Video and I would suggest you use that, instead.
With that said, it is possible that newer tenants simply don't have the feature since the migration is in process already.