The agreement specifically covers the use of "certain Linux-based products" in Samsung devices, the companies said.
Financial details were not disclosed, but both parties will receive monetary payments as compensation for their intellectual property portfolios.
The deal marks a second patent agreement in which Microsoft succeeded in indirectly obtaining licence fees from Linux.
Microsoft has stated publicly that it believes Linux infringes on its intellectual property, although it has never sought to uphold such claims in court.
Although several businesses welcomed the deal, it was met with harsh criticism from open source advocates.
The agreement validates Microsoft's intellectual property claims over Linux, but the critics believe that claims were false to begin with.
The Linux kernel and many other applications that ship with the operating system are governed by the General Public Licence.
An upcoming revision of the licence has been specifically written to prevent patent deals such as those between Microsoft and Novell, and is likely to also block the Samsung agreement.
And, yep, it'll run Android rather than RiscOS
US engineering giant's cost-cutting outsourcing plan is on the rocks, according to insiders
HP Envy X2 laptop only affordable if you've got loadsamoney
Counterfeit code-signing certificates enabling hackers to hide malware being sold by cyber criminals
Certificates can be used as part of layered obfuscation to evade detection by anti-virus software